#include <iostream>
#include <vector>

using namespace std;

// 67. 二进制求和
// 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
// 输入：a = "1010", b = "1011"
// 输出："10101"
class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a);
        reverse(b);

        string ans;
        int c = 0;  // 表示进位
        int i = 0, j = 0;
        while(i < a.size() && j < b.size()) {
            int d = (a[i] - '0') + (b[i] - '0') + c;
            ans.push_back(d % 2 + '0');
            c = d / 2;
            i++; j++;
        }

        while( i < a.size()) {
            int d = (a[i] - '0') + c;
            ans.push_back(d % 2 + '0');
            c = d / 2;
            i++;
        }

        while( j < b.size()) {
            int d = (b[j] - '0') + c;
            ans.push_back(d % 2 + '0');
            c = d / 2;
            j++;
        }

        if( c == 1) {
            ans.push_back('1');
        }
        reverse(ans);
        return ans;
    }

private:
    void reverse(string &a) {
        int i = 0, j = a.size() - 1;
        char tmp;
        while( i < j) {
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;
        }
    }
};
int main() {
//    std::cout << Solution().addBinary("11", "1") << std::endl; // "100"
//    std::cout << Solution().addBinary("1010", "1011") << std::endl; // "10101"
//    std::cout << Solution().addBinary("1", "111") << std::endl; // "1000"
    std::cout << Solution().addBinary("100", "110010") << std::endl; // "1000"

    return 0;
}
